// 组合总和2

package Leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class solution_040 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        link(candidates, target, -1, result, new ArrayList<>());
        return result;
    }

    public void link(int[] candidates, int target, int position, List<List<Integer>> result,
            List<Integer> combination) {
        int sum = 0;
        for (int i : combination) {
            sum += i;
        }
        if (target == sum) {
            for (List<Integer> list : result) {
                if (compare(combination, list) == true)
                    return;
            }
            result.add(new ArrayList<>() {
                {
                    addAll(combination);
                }
            });
        }
        if (target > sum) {
            for (int i = position + 1; i < candidates.length && candidates[i] + sum <= target; i++) {
                // 提前剪枝，但是三个相同失效
                // if (i > 0 && candidates[i] == candidates[i - 1]) {
                // if (!(combination.size() > 0 && combination.get(combination.size() - 1) ==
                // candidates[i]))
                // continue;
                // }
                combination.add(candidates[i]);
                link(candidates, target, i, result, combination);
                combination.remove(combination.size() - 1);
            }
        }
    }

    public boolean compare(List<Integer> a, List<Integer> b) {
        if (a.size() != b.size())
            return false;
        else {
            for (int i = 0; i < a.size(); i++) {
                if (a.get(i) != b.get(i))
                    return false;
            }
        }
        return true;
    }
}

public class Solution040 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        // 使用 List 存储数量，保证有序和下标直取
        List<int[]> freq = new ArrayList<int[]>();
        for (int candidate : candidates) {
            int size = freq.size();
            if (freq.isEmpty() || freq.get(size - 1)[0] != candidate) {
                freq.add(new int[] { candidate, 1 });
            } else
                freq.get(size - 1)[1]++;
        }
        backTrace(freq, target, 0, result, new ArrayList<>());
        return result;
    }

    private void backTrace(List<int[]> freq, int target, int index, List<List<Integer>> result,
            List<Integer> combination) {
        if (target == 0) {
            result.add(new ArrayList<>(combination));
            return;
        } // 这个结果判定一定放在第一个，否则如果 index >= freq.size() 之后程序直接结束，会少记录结果
        if (index >= freq.size() || target < 0)
            return;
        // 1.一次不添加
        backTrace(freq, target, index + 1, result, combination);
        // 2. 添加若干次
        for (int i = 1; i <= freq.get(index)[1]; i++) {
            combination.add(freq.get(index)[0]);
            backTrace(freq, target - i * freq.get(index)[0], index + 1, result, combination);
        }
        // 回溯
        for (int i = 1; i <= freq.get(index)[1]; i++) {
            combination.remove(combination.size() - 1);
        }
    }
}
